A Bloom filter is a well-known space-efficient data structure that answers set membership queries with some chance of false positives. In an attempt to solve many of the implementation constraints faced of next generation networks (e.g., Gbps speeds, increasingly complex tasks, larger systems, high-speed memory availability, etc.), the use of small Bloom filters in packet headers for different purposes (routing, security, accountability, etc.) has been proposed in PCT/EP 2008/061167, PCT/EP2008/063647 (hereinafter “[1]”) and P. Jokela, A. Zahemszky, C. Esteve, S. Arianfar, and P. Nikander, “LIPSIN: Line speed publish/subscribe inter-networking”, In ACM SIGCOMM, Barcelona, August, 2009 (hereinafter “[2]”). The key idea presented in these documents is a novel, space-and-computation-efficient source-routing and packet forwarding mechanism based on link identifiers and small Bloom Filters in packet headers.
In this document, we refer to the Bloom filters that are placed in the packet header, used in these type of applications, as an in-packet Bloom filters (iBF). In a way, an iBF follows a reverse approach compared to traditional BF-based approached previously described in the literature, for example by Broder and Mitzenmacher in Network Applications of Bloom Filters: A Survey. Internet Mathematics (2002) vol. 1 (4) pp. 485-509.
One application scenario, presented in [2], is a publish/subscribe-based network with an MPLS Path Computation Element (PCE) like topology layer that is able to determine source-routed paths. (Publish-Subscribe (“pubsub”) oriented networking, as described by Mikko Särelä, Teemu Rinta-Aho, and Sasu Tarkoma in “RTFM: Publish/Subscribe Internetworking Architecture”, published in the proceedings of ICT Mobile Summit, Stockholm, Jun. 11-13, 2008, focuses on data, as opposed to the original Internet Protocol which focuses on hosts and end points, as primary named entities. One idea behind the Publish-Subscribe paradigm is that one can avoid unwanted data delivery from one node to another. Using globally unique IP addresses, as in today's network, a sender can deliver a data packet to a host identified with an IP address without any explicit request from the receiver. This causes many problems, as it results in a user receiving unwanted, and even possibly malicious, data. This problem could be overcome by abandoning receiver-based addressing, such as used in the IP address scheme, as this removes the possibility of sending data to a destination host without the destination host having requested the data. Another scenario is an energy-efficient and secure replacement for the forwarding fabric in (G)MPLS or Carrier Ethernet.
In the field of data packet forwarding technologies, including IP forwarding, MPLS, and Carrier Ethernet, forwarding is based on the underlying assumption that the network shall always attempt to deliver packets to the destination named in the packet header, independent of who has placed the destination in the packet and where the packet is in the network. In MPLS, however, the situation is somewhat different since the label stack in the packet header works (usually) only at the designated path, as the labels may have different meanings on other paths. However, even in MPLS the network is agnostic to who has sent the packet, when the packet has been sent, and what the packet carries. In other words, the current networks do not provide any kind of protection at the network layer, or the protection provided is inconsequential and weak, as is the case with MPLS networks.
Another inherent security problem in forwarding is that the destination field in the packet header can be easily associated with the receiver. This, together with the potential predictability of other fields, makes traffic analysis relatively easy. In highly secure networks, such as military networks, it is essential to prevent traffic analysis. Today that is typically accomplished with link encryption, which is a relatively expensive operation.
In the field of in-packet Bloom Filters based forwarding, as described in [1-2], the situation is almost similar. There are no security methods to protect the receivers or the network from abuse of in-packet Bloom filters. First, without further considerations at how the iBFs are constructed, an iBF can be simply copied from one packet into another packet, and the resulting packet would be recognized as a legitimate one with respect to the state (elements) it carries.
Second, given two different packets that contain iBFs (as defined in [1]) with the same (or approximately the same) bit distribution, there is a leak of information since an observer can deduce that the same (or an overlapping) set of elements are present in the iBFs of the two different packets. Extending this threat, an attacker may wait and collect a large sample of iBFs to infer some common patterns of the inserted elements or even retrieve the element identities themselves. This, in turn, may allow both construction of forged iBFs and detailed traffic analysis.
Third, in case that an iBF gets compromised, i.e. an attacker has figured out how to construct valid iBFs, a victim is not able to detect and discard un-authorized iBFs nor do they have a way to re-establish the original (distributed) trust on the compromised iBF elements.
Specifically, in the field of forwarding data packets with in-packet Bloom filters, as in general also in other known forwarding methods, this lack of security is critical due to the risk of Distributed Denial of Service (DDoS) attacks, where a victim is flooded with traffic. For example, with an iBF source-routing-based solution, such as the one presented in [1-2], an iBF generated for a specific path is a valid forwarding identifier for all traffic using the same path. Thus, when an attacker obtains a valid iBF, the attacker can use it also for other data to deliver it to the original receiver. Hence, the routing approach based on compact representation of link identifiers is subject to an iBF replication attack. Moreover, there is a lack of native protection against DDoS attacks.
As another specific example, if an attacker can acquire a legitimate working iBF for a path that passes near the attacker and can simultaneously form an approximate iBF from the attacker's present location to the path, the attacker can construct a new iBF that allows it to inject traffic to the specified path, thereby allowing the attacker to flood the receiver with unwanted packets.